In this paper, we study the fundamental problem of gossip in the mobiletelephone model: a recently introduced variation of the classical telephonemodel modified to better describe the local peer-to-peer communication servicesimplemented in many popular smartphone operating systems. In more detail, themobile telephone model differs from the classical telephone model in threeways: (1) each device can participate in at most one connection per round; (2)the network topology can undergo a parameterized rate of change; and (3)devices can advertise a parameterized number of bits about their state to theirneighbors in each round before connection attempts are initiated. We begin bydescribing and analyzing new randomized gossip algorithms in this model underthe harsh assumption of a network topology that can change completely in everyround. We prove a significant time complexity gap between the case where nodescan advertise $0$ bits to their neighbors in each round, and the case wherenodes can advertise $1$ bit. For the latter assumption, we present twosolutions: the first depends on a shared randomness source, while the secondeliminates this assumption using a pseudorandomness generator we prove to existwith a novel generalization of a classical result from the study of two-partycommunication complexity. We then turn our attention to the easier case wherethe topology graph is stable, and describe and analyze a new gossip algorithmthat provides a substantial performance improvement for many parameters. Weconclude by studying a relaxed version of gossip in which it is only necessaryfor nodes to each learn a specified fraction of the messages in the system.
展开▼
